\section{Introducci\'on}

Se nos pidi\'o implementar un algoritmo para maximizar la n\'umero de camiones registrados en un puesto de control por un especialista. Como dicho especialista solo se lo puede contratar por una cantidad fija de d\'ias consecutivos, nuestra tarea es decidir cual ser\'a la fecha idonea para que logre inspeccionar la mayor cantidad de camiones posibles.
\\
\\
La entrada del algoritmo ser\'a la siguiente:
\begin{itemize}
\item Un entero \textbf{D} $\rightarrow$ Representar\'a el n\'umero de d\'ias (consecutivos) que el experto puede quedarse en el puesto de control.
\item Un entero \textbf{n} $\rightarrow$ Representar\'a la cantidad de camiones que pasar\'an por el puesto de control.
\item $n$ enteros \textbf{d$_i$} $\rightarrow$ Representar\'an los d\'ias que pasar\'an los camiones.
\end{itemize}

%\\
%\\
Luego una instancia valida podr\'ia ser la siguiente:
\\
$D = 3$, $n = 5$, $d_1 = 4$, $d_2 = 2$, $d_3 = 4$, $d_4 = 5$, $d_5 = 1$
\\
\\
En este caso tenemos dos soluciones \'optimas:
\begin{itemize}
\item[\textbf{1}] Que el especialsta venga el d\'ia $2$, pudiendo registrar de esta manera $d_2$, $d_1$, $d_3$
\item[\textbf{2}] Que el especialsta venga el d\'ia $4$, pudiendo registrar de esta manera $d_1$, $d_3$, $d_4$
\end{itemize}

%\\
Ya que no nos piden devolver una soluci\'on en particular, podremos devolver cualquiera de las dos.
\\
\\
Las \'unicas restricciones que nos dan son que la complejidad de nuestro algoritmo sea menor que $O(n^2)$ y que el mismo pueda tomar m\'as de una instancia del problema.




\section{Idea General de Resoluci\'on}
La idea que proponemos es bastante simple
\begin{itemize}
\item Usaremos un vector<int> 'camiones' para guardar los d\'ias en que vendr\'an los camiones.
\item Como los d\'ias en la entrada pueden venir en cualquier orden, lo primero que haremos ser\'a ordenar dicho vector de menor a mayor utilizando la funci\'on sort() de la std de c++.
\item Probaremos m\'as adelante que si o si debe existir una soluci\'on \'optima en la cual el d\'ia de contrataci\'on del inspector coincida con la llegada de un cami\'on.
\item Luego para cada uno de los d\'ias en los que llegue un cami\'on supondremos que se contratar\'a al inspector ese mismo d\'ia y calcularemos la fecha en la cual se estar\'ia retirando del puesto de control.
\\Con la ayuda de una simple busqueda binaria buscaremos dentro del vector de camiones el \'ultimo cami\'on registrado por el especialista. 
\item La cantidad de camiones que llegar\'a a registar el inspector antes de irse ser\'a la resta del \'indice del \'ultimo cami\'on registrado y el \'indice del primer d\'ia m\'as uno.
\item Una vez realizado este proceso para todos los d\'ias de llegada de un cami\'on, nos quedaremos con el que maximize la cantidad de camiones registrados y ser\'a la soluci\'on del problema devuelta.
\end{itemize}

\subsection{Ejemplo}

Tomando la siguiente entrada, $D = 3, n = 5$, y los días $d_0=1$, $d_1= 2$, $d_2= 4$, $d_3=4$, $d_4=4$
el algoritmo operar\'ia de la siguiente manera:

\begin{itemize}
\item Toma $d_i$, $i = 0$ como primer d\'ia en el que se contrata al especialista.
\begin{itemize}
\item Se busca binariamente el \'ultimo camion que pasa el dia $3$, o en su defecto el d\'ia m\'as grande menor a $3$.
\item En la b\'usqueda binaria se obtiene el d\'ia $d_1$.
\item Se realiza $1$ (index obtenido por b\'usqueda binaria)~~$-$~$0$~ (index del primero) $+$~$1 = 2$.
\\ Este es el total de camiones registrados por el especialista.
\end{itemize}
\item Se procede a tomar el siguiente d\'ia con $i = 1$
\begin{itemize}
\item Se busca binariamente el \'ultimo cami\'on que pasa el d\'ia $4$, o en su defecto el d\'ia m\'as grande menor a $4$.
\item En la b\'usqueda binaria se obtiene el dia $d_4$.
\item La cantidad de camiones registrados es: $4 - 1 +1$ 
\end{itemize}
\item Se procede a tomar el siguiente d\'ia, $i = 2$
\begin{itemize}
\item Se busca binariamente el \'ultimo cami\'on que pasa el d\'ia $6$, o en su defecto el d\'ia m\'as grande menor a $6$.
\item En la b\'usqueda binaria se obtiene el d\'ia $d_4$.
\item La cantidad de camiones registrados es: $4 - 2 +1 $
\end{itemize}
\item Se procede a tomar el siguiente d\'ia, $i = 3$
\begin{itemize}
\item Se busca binariamente el \'ultimo cami\'on que pasa el d\'ia $6$, o en su defecto el d\'ia m\'as grande menor a $6$.
\item En la b\'usqueda binaria se obtiene el d\'ia $d_4$.
\item La cantidad de camiones registrados es: $4 - 3 +1$ 
\end{itemize}
\item Se procede a tomar el siguiente d\'ia, $i = 4$
\begin{itemize}
\item Se busca binariamente el \'ultimo cami\'on que pasa el dia $6$, o en su defecto el d\'ia m\'as grande menor a $6$.
\item En la b\'usqueda binaria se obtiene el d\'ia $d_4$.
\item La cantidad de camiones registrados es: $4 - 3 +1$
\end{itemize}
\item La mayor cantidad de camiones registrados ocurre el dia $d_1$. 
\end{itemize}


\newpage

\section{Pseudoc\'odigo}

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void funcionPrincipal()}

  \STATE{int diaMax, cantMax, indiceUltimoDia = 0}
  \STATE{Ordeno el vector 'camiones' de menor a mayor}

  \STATE{\textbf{Para todo} $i \in \{0 , n-1\}$}
    \STATE{\quad Tomo el d\'ia camiones[i] como primer d\'ia de contrataci\'on}  
    \STATE{\quad UltimoDia = camiones[i]+diasInspector}
    \STATE{\quad Realizo una busqueda binaria sobre el vector de camiones para obtener indiceUltimoDia}
    \STATE{\quad \textbf{Si} $IndiceDelUltimoDia - i +1$ > cantMax \textbf{entonces}}
      \STATE{\quad \quad cantMax = $IndiceDelUltimoDia - i +1$}
      \STATE{\quad \quad diaMax = camiones[i]}

  \STATE{Devuelvo diaMax y cantMax}
    



\end{algorithmic}
\end{algorithm}



\section{Cota de Complejidad}

Al recibir la entrada crearemos un vector de enteros de n posiciones, dicha tarea tiene una complejidad de $O(n)$
\\
\\
Para ordenar el vector 'camiones' utilizamos la funci\'on sort de la std de c++, la misma tiene una complejidad temporal de $O(n \log(n))$ seg\'un su documentaci\'on.
\footnote{http://www.cplusplus.com/reference/algorithm/sort/}
\\
\\
Mas tarde iteraremos $i$ n veces, y dentro de cada iteraci\'on llamaremos a una simple busqueda binaria con complejidad $O(\log(n))$.
\\
Luego nuestro 'for' tendra una complejidad de O(n log(n))
\\
\\
Finalmente el resultado: $O(n) + O(n \log(n)) + O(n \log(n)) = O(n \log(n)) \subset O(n^2)$. 


\section{Correctitud}

Antes que nada debemos demostrar que existe una soluci\'on \'optima tal que la misma comienza el mismo d\'ia en que llega alguno de los camiones.


\begin{itemize}

\item Supongo que existe una solucion \'optima que maximice la cantidad de camiones registrados y que empieze el d\'ia $p$

\item Ahora, en el día $p$ pueden ser registrados camiones o no.
\\
En el caso de que sean registrados camiones ese día, queda demostrado.
\item En caso de que no, sumo uno a $p$. $(*)$\\
Esta soluci\'on tambi\'en es \'optima, ya que en el d\'ia $p$ no hab\'ia camiones para registrar.

\item Si en $p+1$ hay camiones queda demostrado. En caso de que no, se realiza $(*)$ de manera recursiva.

\item Luego queda demostrado que existe una soluci\'on \'optima tal que la misma comienza el mismo d\'ia en que sale alguno de los camiones.
\end{itemize}
%\\
Entonces, el algoritmo planteado para el problema, que solo toma los d\'ias en que salen camiones, forzosamente llegar\'a a encontrar una soluci\'on \'optima.

\newpage

\section{Testing}
\subsection{Caso Random}

Para testear la correctitud de nuestro algoritmo se cre\'o un generador de entradas que fabricar\'a 100 instancias random con N camiones y comparara nuestra salida con la de otro algoritmo creado por nosotros que resolviera el problema utilizando fuerza bruta pero con una complejidad mas alta.\\
\\
Los resultados comprobaron que nuestro algoritmo devuelve la soluci\'on correcta en todos los casos.
\\
\\
Ejemplo de caso random: (Este en particular tambi\'en fue verificado a mano)
\\
\\
\begin{tabular}{| l | l |}
\hline
Entrada ~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~4 10 6 7 13 7 7 2 14 5 6 5 \\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Camiones ordenado ~ $\longrightarrow\ $ ~2 5 5 6 6 7 7 7 13 14 ~~~~~~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Salida ~~~~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~5 7 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\ \hline
\end{tabular}


\subsection{Pocos o ning\'un cami\'on}

\begin{tabular}{| l | l |}
\hline
Entrada ~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~5 0 ~~~~~~~\\ \hline
\end{tabular}
\quad \quad \quad \quad \quad \quad
\begin{tabular}{| l | l |}
\hline
Entrada ~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~5 1 3 ~~~~~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Camiones ordenado ~ $\longrightarrow\ $ ~ --- ~~~~~~~\\ \hline
\end{tabular}
\quad \quad \quad \quad \quad \quad
\begin{tabular}{| l | l |}
\hline
Camiones ordenado ~ $\longrightarrow\ $ ~ 3 ~~~~~~~~~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Salida ~~~~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~0 0 ~~~~~~~\\ \hline
\end{tabular}
\quad \quad \quad \quad \quad \quad
\begin{tabular}{| l | l |}
\hline
Salida ~~~~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~3 1 ~~~~~~~\\ \hline
\end{tabular}
\\
\\
Queriamos ver si nuestro algoritmo funcionaba correctamente y no se tildaba cuando la entrada era lo m\'as chica posible y la soluci\'on trivial.


\subsection{Dos soluciones \'optimas}

\begin{tabular}{| l | l |}
\hline
Entrada ~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~2 4 5 6 1 2 ~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Camiones ordenado ~ $\longrightarrow\ $ ~1 2 5 6 ~~~~~~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Salida ~~~~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~1 2 ~~~~~~~~~~~\\ \hline
\end{tabular}
\\
\\
Queriamos ver cual de las dos soluciones devolv\'ia nuestro algoritmo. Siempre devolver\'a la que empieze con el d\'ia mas chico.

\subsection{El inspector revisa todos los camiones}
\begin{tabular}{| l | l |}
\hline
Entrada ~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~8 4 5 6 1 2 ~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Camiones ordenado ~ $\longrightarrow\ $ ~1 2 5 6 ~~~~~~\\ \hline
\end{tabular}
\\
\begin{tabular}{| l | l |}
\hline
Salida ~~~~~~~~~~~~~~~~~~~ $\longrightarrow\ $ ~1 4 ~~~~~~~~~~~\\ \hline
\end{tabular}
\\
\\
Chequeamos el caso borde donde el inspector lograr\'a inspeccionar todos los camiones si viene el primer d\'ia


\newpage
\section{Resultados}

\begin{itemize}
\item En primera instancia se decidi\'o corroborar emp\'iricamente que la complejidad de nuestro algoritmo solo depende de la cantidad de camiones que lleguen.
\\
\\
Para ello se decidi\'o dejar fija la misma (en 100) e ir variando la cantidad de d\'ias que se quedar\'a el inspector:
\end{itemize}
\includegraphics[width=18cm]{./camionesSospechosos/graph_ej1_2.png}
\\
\quad $~~~~~~~$ Los resultados fueron los esperados, el tiempo siempre fue constante para todos los casos.
\begin{itemize}
\item Luego se decidi\'o medir los tiempos de ejecuci\'on variando la cantidad de camiones y dejando los d\'ias del inspector fijo:
\end{itemize}
\includegraphics[width=18cm]{./camionesSospechosos/graph_ej1_1.png}
\\
\includegraphics[width=18cm]{./camionesSospechosos/graph_ej1_3.png}
\\
\\
\quad $~~~~~~~$ Observando los gr\'aficos anteriores se puede apreciar claramente que el tiempo de ejecuci\'on de nuestro\\
\quad $~~~~~~~$ algoritmo en funci\'on de la cantidad de camiones se asemeja bastante al gr\'afico de una funci\'on lineal.
\begin{itemize}
\item Para todas las valores se generaron aleatoreamente 20 instancias de prueba. Los tiempos fueron medidos en microsegundos y se calcul\'o el promedio.
\end{itemize}



\section{Adicionales}
Esta vez el experto a contratar nos permite dividir el tiempo de contrato en dos periodos no necesariamente consecutivos. 
Lo que quiere decir, si antes se lo podía contratar en un periodo de $D$ días consecutivos, ahora puede ofrecer su servicio en dos intervalos de $K$ y $D-K$ días (con $0 \leq K  \leq D$)

\begin{enumerate}
\item ¿Cómo debería modificarse el algoritmo implementado, si en lugar de elegir un unico intervalo de \textit{D} días, se permite elegir 2 intervalos distintos, tal como se indica?. 
\begin{itemize}
\item El algoritmo original recorre la secuencia ordenada de los camiones. Al ubicarse en una posición lo cuenta como si fuese el primer día de inspección, entonces con una busqueda binaria encuentra el último. Pero esto lo hace para un intervalo fijo de tiempo.
\item Podemos modificar el algoritmo de la siguiente manera:
\begin{itemize}
\item Para cada intervalo $K$ (primer intervalo de tiempo) con $0 \leq K  \leq (D-1)$ recorremos cada posición del arreglo como veniamos haciendo, suponiendo la posición $i$ como primer dia de revisación, luego la busqueda binaria para hallar el ultimo día. 
Antes de pasar a la siguiente iteración hacemos el mismo procedimiento para el segundo intervalo de tiempo, con los casilleros a la derecha del último en primer intervalo.
\item Luego vamos guardando el mejor resultado.
\end{itemize} 

\item Este psudocódigo nos muestra la idea de la modificación:

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void funcionPrincipal()}

  \STATE{int diaMax, cantMax, indiceUltimoDia = 0}
  \STATE{Ordeno el vector 'camiones' de menor a mayor}
  \STATE{\textbf{Para todo} $k \in \{0 , D-1\}$}
	  \STATE{\textbf{Para todo} $i \in \{0 , n-1\}$}
		\STATE{\quad Tomo el d\'ia camiones[i] como primer d\'ia de contrataci\'on}  
		\STATE{\quad UltimoDia = camiones[i]+k}
		\STATE{\quad Realizo una busqueda binaria sobre el vector de camiones para obtener indiceUltimoDia}
		\STATE{\quad \quad guardo $IndiceUlt1$, y $cantEnPrimerIntervalo$}
		\STATE{\textbf{Para todo} $j \in \{IndiceDelUltimoDia , n-1\}$}
		  \STATE{\quad \quad Hago exactamente lo mismo que en bloque superior para encontrar el segundo intervalo D-k}
		  \STATE{\quad \quad guardo $IndiceUlt2$, y $cantEnSegundoIntervalo$}
		  \STATE{\quad \textbf{Si} $cantCamionesEnSegundoIntervalo + cantEnSegundoIntervalo$ > cantMax \textbf{entonces}}
		  \STATE{\quad \quad Actualizo $CantMax$ y guardo intervalos}
		  
  \STATE{Devuelvo diaMax y cantMax}

\end{algorithmic}
\end{algorithm}

\end{itemize}

\item ¿Cómo afectan estos cambios la complejidad del algoritmo?. 
\begin{itemize}
\item El algoritmo original tenia una complejidad de $O(nlog(n))$.
\item En este caso, para cada posición $i$ del arreglo realiza una busqueda binaria mas $n-r$ busqueda binaria, donde $r$ es el índice del último camión en posición $i$.
\item sabemos que $i \leq r \nleq $, sabemos que el peor caso sría si en el intervalo K actual, solo se puede registrar un solo camión ($i=r$).
\item Dado un $K$ como primer intervalo, en la primera iteración realiza $1 BusqBin + (n-1)BusqBin$ como mucho. Donde $BusqBin$ es la busquda binaria.
\item Con ese mismo $K$ en la segunda iteración hace $1 BusqBin + (n-2)BusqBin$ como mucho.
\item En la iteración $i$ hace $1 BusqBin + (n-i)BusqBin$, asi para todo $i$ hasta $n$.
\item entonces para cada $K$ realiza $n BusqBin + (n*(n+1)/2) BusqBin$
\item $T(n,D)= (D-1)*(n+(n*(n+1)/2))*T(BusqBin)$.
\item $T(n,D)= (D-1)*(n+((n^2+n)/2))*O(log(n))$.
\item $T(n,D)= (D-1)*(n^2)*O(log(n))$.
\item la complejidad del algoritmo es $O((D-1)*(n^2)*log(n))$
 
\end{itemize}

\end{enumerate}


